#include<iostream>
#include<vector>
using std::vector;
using std::endl;
using std::cout;

void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
int part(vector<int>&arr, int low, int hight)  //划分函数
{
	int i = low, j = hight, pivot = arr[low]; //基准元素
	while (i < j)
	{
		while (i<j && arr[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(arr[i++], arr[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && arr[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(arr[i], arr[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}

void Quicksort(vector<int>&arr, int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = part(arr, low, hight);  // 返回基准元素位置
		Quicksort(arr, low, mid - 1); // 左区间递归快速排序
		Quicksort(arr, mid+1, hight); // 右区间递归快速排序
	}
}

template<class con>
void dispaly(con&c){
    for(auto &ele : c){
        cout<<ele<<" ";
    }
    cout<<endl;
}

int test0(){
    vector<int>arr ={12,1,7,9,18,22,25};
    dispaly(arr);
    Quicksort(arr,0,arr.size()-1);
    dispaly(arr);
}

int main(void){
    test0();
}